﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.IO;
using System.Threading.Tasks;

namespace TesteC
{
    class Node
    {
        public float value;
        public float room;
        public float estimate;
        public int itemId;
        public bool isVisited;
        public Node parent;
        public Node left;
        public Node right;
    }

    class Tree
    {
        public Node root;
    }


    class Program
    {
        static string curFile = "";
        static void Main(string[] args)
        {
            /*
            DirectoryInfo d = new DirectoryInfo(@"C:\dev\coursera\knapsack\Knapsack\Knapsack\bin\Debug\data");
            FileInfo[] fs = d.GetFiles();
            for (int i = 0; i < fs.Length; i++)
            {
                FileInfo f = fs[i];

                curFile = f.FullName;
                doSolve(f.FullName);
            }*/
           // doSolve("tmp.data");
             doSolve("C:/dev/coursera/knapsack/Knapsack/Knapsack/bin/Debug/data/ks_19_0");
            //doSolve("G:/discrete-optimization/knapsack/data/ks_4_0");
            
        }

        static void doSolve(string file)
        {
            using (StreamReader sr = new StreamReader(file))
            {
                using (StreamWriter sw = new StreamWriter("resp.txt"))
                {
                    int nItems = 0;
                    int knapSize = 0;
                    int[] values;
                    int[] weights;

                    string line = sr.ReadLine();
                    string[] s = line.Split();
                    nItems = int.Parse(s[0]);
                    knapSize = int.Parse(s[1]);
                    values = new int[nItems];
                    weights = new int[nItems];

                    int k = 0;

                    for (int kk = 0; kk < nItems; kk++)
                    {
                        line = sr.ReadLine();
                        s = line.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
                        values[k] = int.Parse(s[0]);
                        weights[k] = int.Parse(s[1]);
                        k++;
                    }

                    System.Diagnostics.Stopwatch swKnap = new System.Diagnostics.Stopwatch();
                    swKnap.Start();
                    float bestVal = 0; int[] sol = new int[] { 1, 2, 3 };

                    if (false)
                    {
                        solveKnapsack(knapSize, values, weights, out bestVal, out sol);
                    }
                    else
                    {
                        solveKnapsack2(knapSize, values, weights, out bestVal, out sol);
                    }

                    swKnap.Stop();


                    sw.WriteLine(bestVal.ToString() + " 1");
                    string ss = sol[0].ToString();
                    for (int i = 1; i < sol.Length; i++) ss += " " + sol[i].ToString();
                    sw.WriteLine(ss);
                }
            }
        }

        static void solveKnapsack2(int knapSize, int[] values, int[] weights, out float bestVal, out int[] sol)
        {
            bestVal = calculateBestValue(knapSize, values, weights);
            Tree myTree = new Tree();
            Node root = new Node();
            root.estimate = bestVal;
            root.value = 0;
            root.room = knapSize;
            root.parent = null;
            root.left = new Node();
            root.left.parent = root;
            root.right = new Node();
            root.right.parent = root;
            myTree.root = root;

            explore(root, values, weights, knapSize, bestVal, 0);

            sol = new int[values.Length];
        }

        static void Analyze(Node node, int[] values, int[] weights, int knapSize, float bestValueSoFar, int depth)
        {
            if (node.room + weights[node.itemId] < knapSize)
            {
                node.value += values[node.itemId];
                node.room -= weights[node.itemId];
                node.isVisited = true;
                node.itemId = node.itemId + 1;
                if (node.value > bestValueSoFar)
                {
                    bestValueSoFar = node.value;
                }
            }
        }

        static void explore(Node node, int[] values, int[] weights, int knapSize, float bestValueSoFar, int depth)
        {
            Analyze(node.left, values, weights, knapSize, bestValueSoFar, depth + 1);
            Analyze(node.right, values, weights, knapSize, bestValueSoFar, depth + 1);


            if (!node.left.isVisited)
            {
                node.left.isVisited = true;

                

                explore(node.left, values, weights, knapSize, bestValueSoFar);
            }
            
            if (!node.right.isVisited)
            {

            }
            else
            {
                if (node.parent != null)
                {
                    explore(node.parent, values, weights, knapSize, bestValueSoFar);
                }
                else
                {
                    int imDone = 1;
                }
            }
        }

        static float calculateBestValue(int knapSize, int[] values, int[] weights)
		{
			SortItemsByValuePerWeight(values, weights);
		
			float curWeight = 0;
            float bestValue = 0;
			int i = values.Length - 1;
			
			while (curWeight < knapSize)
			{
				if (weights[i] + curWeight < knapSize)
				{
					curWeight += weights[i];
					bestValue += values[i];
				}
				else
				{
					float pct = (knapSize - curWeight) / weights[i];
					curWeight += pct * weights[i];;
					bestValue += pct * values[i];
					break;
				}
				i--;
			}
			
			return bestValue;
		}

        static void SortItemsByValuePerWeight(int[] values, int[] weights)
        {
            float[] valuePerWeight = new float[values.Length];

            for(int i = 0; i < values.Length; i++)
            {
                valuePerWeight[i] = (float)values[i] / (float)weights[i];
            }

            float[] valuePerWeight2 = new float[valuePerWeight.Length];
            Array.Copy(valuePerWeight, valuePerWeight2, valuePerWeight.Length);

            Array.Sort(valuePerWeight, values);
            Array.Sort(valuePerWeight2, weights);
        }

        static void solveKnapsack(int knapSize, int[] values, int[] weights, out float bestVal, out int[] sol)
        {
            int[,] grid = new int[values.Length + 1, knapSize + 1];

            for (int capacity = 0; capacity < knapSize + 1; capacity++)
            {
                grid[0, capacity] = 0;
            }

            for (int itemId = 0; itemId < values.Length; itemId++)
            {
                for (int capacity = 0; capacity < knapSize + 1; capacity++)
                {
                    int valueIfITakeTheItem = 0;
                    int valueifIDoNotTakeTheItem = 0;

                    valueifIDoNotTakeTheItem = grid[itemId, capacity];

                    if (capacity - weights[itemId] >= 0)
                    {
                        valueIfITakeTheItem = grid[itemId, capacity - weights[itemId]] + values[itemId];
                    }

                    grid[itemId + 1, capacity] = Math.Max(valueIfITakeTheItem, valueifIDoNotTakeTheItem);
                }
            }

            bestVal = grid[values.Length, knapSize];

            //traceback
            int currentItem = values.Length;
            int currentCapacity = knapSize;

            sol = new int[values.Length];
            while (currentItem > 0)
            {
                if (grid[currentItem, currentCapacity] == grid[currentItem - 1, currentCapacity])
                {
                    sol[currentItem - 1] = 0;
                   
                }
                else
                {
                    sol[currentItem - 1] = 1;
                    currentCapacity -= weights[currentItem - 1];
                }
               
                currentItem--;
            }
            
        }
    }
}